public class Huiwen {
    // 定义链栈节点类
    static class Node {
        char data;// 数据域，存储字符
        Node next;// 指针域，指向下一个节点

        // 构造方法
        public Node(char data) {
            this.data = data;
            this.next = null;
        }
    }

    // 定义链栈类
    static class Stack {
        Node top; // 栈顶指针

        // 构造方法，初始化空栈
        public Stack() {
            this.top = null;
        }

        // 判断栈是否为空
        public boolean isEmpty() {
            return top == null;
        }

        // 入栈操作
        public void push(char data) {
            Node newNode = new Node(data); // 创建新节点
            newNode.next = top; // 新节点指向当前栈顶
            top = newNode;  // 更新栈顶指针
        }

        // 出栈操作
        public char pop() {
            if (isEmpty()) {
                throw new IllegalStateException("栈为空，无法出栈");
            }
            char data = top.data;// 获取栈顶数据
            top = top.next;// 更新栈顶指针
            return data;// 返回出栈数据
        }
    }
    // 判断字符串是否是回文字符串
    public static boolean isPalindrome(String str) {
        Stack stack = new Stack(); // 创建链栈
        int length = str.length(); // 获取字符串长度

        // 将字符串的前半部分字符入栈
        for (int i = 0; i < length / 2; i++) {
            stack.push(str.charAt(i));
        }
        // 如果字符串长度为奇数，跳过中间字符
        int start = length % 2 == 0 ? length / 2 : length / 2 + 1;

        // 依次比较栈顶元素和字符串后半部分的字符
        for (int i = start; i < length; i++) {
            if (stack.isEmpty() || stack.pop() != str.charAt(i)) {
                return false; // 如果不匹配，返回false
            }
        }
        return true; // 如果全部匹配，返回true
    }

    public static void main(String[] args) {
        // 测试数据
        String[] testStrings = {
                "99111222aaaabbbbXabaabbbb22211199",
                "aabbccdd11222211ddccbbaa"
        };

        // 测试每个字符串是否是回文
        for (String str : testStrings) {
            if (isPalindrome(str)) {
                System.out.println("字符串 \"" + str + "\" 是回文字符串");
            } else {
                System.out.println("字符串 \"" + str + "\" 不是回文字符串");
            }
        }
    }
}
